package F.树;

import java.util.LinkedList;
import java.util.Queue;

public class _543_二叉树的直径 {
    /**
     * 自解：最左下的叶子结点到最右下的叶子结点，因此转化为找叶子结点，再转化为求取左子树和右子树的层数
     * 最终的直径=左层数+右层数
     * @param root
     * @return
     *
     *
     * 解答错误：当出现严重的一边偏 并且茂密的一边具有最长时
     * ---主方法中添加递归 依次计算每个结点的直径 输出最大值
     * 耗时有点久
     *
     * 因为每次都要层次遍历
     */

    int max = Integer.MIN_VALUE;
    public int diameterOfBinaryTree(TreeNode root) {


        if (root == null ){
            return 0;
        }

        if (root.left == null && root.right == null){
            return 0;
        }

        if (getLevel(root.left)+getLevel(root.right) > max){
            max = getLevel(root.left)+getLevel(root.right);
        }

        diameterOfBinaryTree(root.left);
        diameterOfBinaryTree(root.right);

        return max;

    }

    public int getLevel(TreeNode root){
        if (root == null){
            return 0;
        }

        int level =0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()){

            int size = queue.size();
            while (size>0){
                TreeNode node = queue.poll();

                if (node.left != null){
                    queue.add(node.left);
                }

                if (node.right != null){
                    queue.add(node.right);
                }

                size--;
            }
            level++;
        }

        return level;
    }

    /**
     * 因为上面的方法中 每一次都要层次遍历 所以效率太慢
     *
     * 题解：经过结点最多的路径就是左子树的深度加右边的深度 最大值
     * 深度的求法：「左边，右边」最大深度+1
     *
     */
    int ans=0;
    public int diameterOfBinaryTree1(TreeNode root) {
        depth(root);

        return ans;

    }
    public int depth(TreeNode root){
        if (root == null){
            return 0;
        }

        int L= depth(root.left);
        int R = depth(root.right);

        ans = Math.max(ans,L+R);

        return Math.max(L,R)+1;
    }


}
